package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * @ClassName: _1122_Relative_sort_array
 * @Description: 1122. 数组的相对排序
 * 给你两个数组，arr1 和 arr2，
 * <p>
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 * <p>
 * 示例：
 * <p>
 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
 * <p>
 * https://leetcode-cn.com/problems/relative-sort-array/
 * @Author: shouzimu
 * @Date: 2020/11/14 9:30
 */
public class _1122_Relative_sort_array {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> valueMap = new HashMap<>(arr2.length);
        for (int i = 0; i < arr2.length; i++) {
            valueMap.put(arr2[i], i);
        }
        Integer[] integers = new Integer[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            integers[i] = arr1[i];
        }
        int l2 = arr2.length;
        Arrays.sort(integers, Comparator.comparingInt(t -> valueMap.getOrDefault(t, t + l2)));
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = integers[i];
        }
        return arr1;
    }


    /**
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArraySlow(int[] arr1, int[] arr2) {
        Map<Integer, Integer> valueMap = new HashMap<>(arr2.length);
        for (int i = 0; i < arr2.length; i++) {
            valueMap.put(arr2[i], i);
        }
        int len = arr1.length;
        int temp;
        for (int i = 0; i < len - 1; i++) {
            boolean swap = false;
            for (int j = 0; j < len - 1 - i; j++) {
                int t1 = valueMap.getOrDefault(arr1[j], arr1[j] + arr2.length);
                int t2 = valueMap.getOrDefault(arr1[j + 1], arr1[j + 1] + arr2.length);
                if (t1 > t2) {
                    temp = arr1[j];
                    arr1[j] = arr1[j + 1];
                    arr1[j + 1] = temp;
                    swap = true;
                }
            }
            if (!swap) {
                break;
            }
        }
        return arr1;
    }


    @Test
    public void relativeSortArrayTest() {
        int[] arr1 = new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
        int[] arr2 = new int[]{2, 1, 4, 3, 9, 6};

        int[] expect = new int[]{2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19};
        Assert.assertArrayEquals(relativeSortArray(arr1, arr2), expect);
    }


    public int[] relativeSortArray3(int[] arr1, int[] arr2) {
        Map<Integer, Integer> valueMap = new HashMap<>(arr2.length);
        for (int i = 0; i < arr2.length; i++) {
            valueMap.put(arr2[i], i);
        }
        List<Integer> integerList = new ArrayList<>(arr1.length);
        for (int i : arr1) {
            integerList.add(i);
        }
        int l2 = arr2.length;
        integerList.sort(Comparator.comparingInt(t -> valueMap.getOrDefault(t, t + l2)));
        for (int i = 0; i < integerList.size(); i++) {
            arr1[i] = integerList.get(i);
        }
        return arr1;
    }
}
